Binary arithmetic encoding is one compression encoding technique. In binary arithmetic encoding, one multivalued symbol is subjected to binarization to generate a binary symbol string, and this binary symbol string is then subjected to arithmetic encoding to obtain a final binary arithmetic code. Arithmetic code has a higher processing cost than Huffman code and has only been employed in applications that do not demand real-time capabilities, examples being file compression and still picture compression. However, with the higher speeds realized in LSI in recent years, arithmetic code has come to be used in the encoding of images. One example is the Main Profile of International Standards H.264 of the new video codec that was established by the International Telecommunication Union Telecommunication Standardization Sector (ITU-T).
In H. 264, binary arithmetic coding is called “Context-based Adaptive Binary Arithmetic Coding (CABAC)”. Details regarding CABAC have been described in International Conferences on Image Processing (ICIP) of the IEEE under the title of “Context-based adaptive binary arithmetic coding in JVT/H. 26L” by D. Marpe et al. at the 2002 conference (2002 IEEE International Conference on Image Processing, ISBN:0-7803-7623-4 IEEE Catalog No. 02CH37396, pages 2-513-2-536); and under the title of “Video compression using context-based adaptive arithmetic coding” at the 2001 conference (2001 IEEE International Conference on Image Processing, ISBN: 0-7803-6725-1, pages 558-561).
In CABAC, multivalued symbols that are to be encoded first undergo binarization to a string of binary symbols (Bin), and each Bin then undergoes binary arithmetic encoding in accordance with probability estimate values for contexts that are determined for each Bin. In binarization, numbers are set to a format that is stipulated by formulas to convert multiple values to a bit pattern, but this can be considered as simple variable-length coding (VLC). Circumstances that can be used in the selection of contexts include the object of representation of the original multivalued symbols, the parameters of surrounding blocks, and the order in a binary symbol string. In decoding, on the other hand, probability estimate values are found from the contexts of the binary symbols that are now to be decoded and the arithmetic code is then decoded. If the binary symbols are restored, the probability estimate values are updated, and further, the contexts of the binary symbols that are to be decoded next are selected.
In ideal arithmetic encoding, data can be compressed to the limit of entropy, and infinite Bin can be logically expressed by one bit. However, because this is difficult to package in practice, in CABAC, simplified arithmetic encoding is adopted and an upper limit is placed on the average number of Bin per bit. For simplification, multiplication is substituted by referring to tables, and the computation required for decoding one Bin is thus limited to referring to tables, comparison, and subtraction.
In binary arithmetic encoding such as H. 264 CABAC, the processing cost of decoding and encoding arithmetic code is high.
FIG. 1 shows the overall configuration of an H. 264 decoder.
An H. 264 decoder is of a configuration that includes: CPB buffer 41 for receiving and holding a stream; and instant decoder 42 for decoding each frame by frame intervals. Instant decoder 42 is made up from CABAC decoder 43 and block decoder 44. Block decoder 44 performs reverse quantizing, inverse discrete integer transform, motion compensation prediction, and an in-loop filter process, and has a processing cost that is proportional to the number of picture elements.
In contrast, the processing cost of CABAC decoder 43 is proportional to the number of Bin.
FIG. 2 shows the details of a CABAC decoder.
CABAC decoder 51 is made up from binary arithmetic code decoder 54, reverse binarization unit 55, memory 52 for saving probability estimate values for each context; and control unit 53 for controlling these components. The processing unit is the decoding of Bin, and control unit 53 both updates the probability estimate values with each decoding of Bin, and further causes internal state to transition in accordance with the grammar of the H. 264 standards. These processes cannot be carried out together for a plurality of Bin, and the number of Bin therefore determines the processing cost.
The actual processing cost is next calculated. The compression rate for each frame differs with the coding type of the frames (within frames or between frames) and the degree of prediction accuracy or image quality, and the number of bits in each frame therefore fluctuates with each frame. In other words, the processing cost of a CABAC decoder fluctuates with each frame. According to the standard, the maximum number of bits for one frame is given by:2048×Max MBPS×Delta Time×Chroma Format Factor/MinCR,and if this is converted to the maximum bit rate for the frame interval average, then:2048×Max MBPS×Chroma Format Factor/MinCR.Here, Max MBPS is the maximum number of macroblocks per second, Delta Time is the frame time interval, Chroma Format Factor is the sample number ratio when a color signal is added to the luminance signal, and MinCR is the minimum compression rate.
In Level 4.1 described in Annex A, Max MBPS is 245760, Chroma Format Factor is 1.5, and MinCR is 2, with the result that the maximum bit rate is 377 Mbps. The Bin-to-bit compression rate is prescribed to be 1.33 or less, and converting this to the maximum Bin rate yields 503 Mbin/sec. Because the maximum bit rate is found from the frame interval average, the maximum Bin rate in this case is a value obtained by dividing the number of Bin that are to be processed in the frame interval average by the frame interval. If the performance of the decoder cannot attain this maximum Bin rate, the decoding process will not be completed by the time that the frame is to be displayed, resulting in the deletion of the frame, i.e., a severe deterioration in image quality.
The preceding explanation regarding the packaging of a decoder also applies for the case of an encoder for performing the reverse operation.
FIG. 3 shows the configuration of an H. 264 encoder.
Block encoder 63 performs such operations as motion compensation prediction, discrete integer transform, quantization, reverse quantization, inverse discrete integer transform, and an in-loop filter process at the rate of picture element input. Block information is then converted to a Bin string by binary converter 64. The Bin string is converted to a coded bit string by arithmetic encoder 65, and then sent to output buffer 66. The amount of accumulation of output buffer 66 is fed back to block encoder 63 and used in the control of the coding amount in block encoder 63.
In binarization, one element of block information, such as the conversion coefficient, is converted to a plurality of Bin. As a result, the generation speed of a Bin string is at least ten times the picture element rate in bursts. Control unit 62 that subsequently handles the Bin string, as well as memory 61 and arithmetic encoder 65, must operate at this speed. If the processing between frames is considered, the maximum Bin rate of an H. 264 encoder is 503 Mbin/sec, the same as for an H. 264 decoder.
In the prior art, real-time processing at high bit rates is still problematic. For example, if the decoding process is performed as prescribed in the H. 264 standards, the Bin rate that is to be processed becomes an unrealistic value. The maximum Bin rate that satisfies the H. 264 Level 4.1 standard is 503 Mbin/sec, and even if one Bin were processed in two cycles, a CABAC decoder or arithmetic encoder must be operated at a frequency of 1 GHz or more. This value is a speed that is several times greater than can be readily realized at low cost by current LSI.